COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	{⊂C<N αOCCULT λ30 P47 I425,0 JC FA}      SECTION 4.
C00009 00003	
C00011 00004	⊂4.1	Initialization for Hidden Line Elimination.⊃
C00017 00005	⊂4.2	Hide Marking a Coherent Object.⊃
C00022 00006	⊂4.3	Edge-Edge and Face-Vertex Comparing.⊃
C00025 00007		An alternate edge-edge  compare method would be to  solve the
C00028 00008	⊂4.4	Recursive Windowing.⊃
C00032 00009	⊂4.5	Photometric Modeling and Video Generation.⊃
C00035 00010	⊂4.6	Performance of OCCULT and Related Work.⊃
C00037 ENDMK
C⊗;
{⊂C;<N; αOCCULT; λ30; P47; I425,0; JC; FA}      SECTION 4.
{JC; FD}   HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
{λ7; W250; JA; FA}
	4.0	Introduction to Hidden Line Elimination.
	4.1	Initialization for Hidden Line Elimination.
	4.2	Hide Marking a Coherent Object.
	4.3	Edge-Edge and Face-Vertex Comparing.
	4.4	Recursive Windowing.
	4.5	Photometric Modeling and Video Generation.
	4.6	Performance of OCCULT and Related Work.
{λ30;W0;I950,0;JUFA}
⊂4.0	Introduction to Hidden Line Elimination.⊃

	Hidden line elimination  refers to the process  of simulating
the  appearance  of  opaque  three  dimensional  objects. The  phrase
<hidden line elimination> dates  from when the problem only  involved
deleting the  undesired,  that  is the <hidden>  lines,  from  a line
drawing; today  the phrase persists but connotes the wider problem of
synthesizing  realistic  images  using  a  computer.     The  present
discussion  is about  techniques  which have  been  implemented in  a
particular hidden  line  eliminator  named  OCCULT,  since  the  word
<OCCULT> means  <to hide>.   Employing  the GEOMED  routines and  the
winged  edged polyhedron  representation,   OCCULT  illustrates novel
solutions to the graphics problems of exploiting object coherence and
image  coherence,     of  combining  image  space   and  model  space
techniques,   and of spatial sorting of  faces, edges and vertices in
two dimensions.

	OCCULT is further  characterized by its  intended application
to   computer  vision  and  robotics.     The  distinguishing  design
requirement of  a hidden  line eliminator  intended for  verification
vision is  that it  must maintain  back pointers  from the  final 2-D
images  to  the initial  3-D  models so  that the  identity  of image
features can  be  recovered. In  computer  graphics, the  results  of
hidden  line  elimination  are  intended  for human  viewing  so  the
correspondence between  the  image and  the  model is  not  retained.
Another design  goal for  OCCULT was  to output  a coherent graph  of
regions,   edges and  vertices that covered  the image  with no holes
missing,   no regions  overlapping and  no dangling  edges.   It  was
naively assumed  that such a highly  structured image representation,
called a  <mosaic image>, would provide a suitable basis for deriving
data such  as the  location and  orientation of  high contrast  edges
without having to generate video images.

	The idea of using a hidden line eliminator in a vision system
is  not new and  has appeared  in two other  vision systems,   one by
[Roberts] and one by [Falk]; the  present system is a direct heir  of
the work  of both Roberts  and Falk in that  the last version  of the
Falk  system  contained  one  of the  early  versions  of  OCCULT (as
installed by Richard Orban). I  reject the view that the  hidden line
elimination  problem  has  been  adequately  solved;  as  with  image
anaylsis, image synthesis (i.e. hidden line elimination), is going to
continue to  be a  perenial research  problem because  it can not  be
fully isolated from  physical modeling.  Metaphorically,  hidden line
elimination is the visible tip of the iceberg of physical simulation.
The weaknesses of  the underlying model literally show  up in passing
through  the process of image synthesis.   The present day collection
of  techniques  are  still  quite  lacking  in   realism,    economy,
flexibility and even reliability.

	OCCULT is  not a  simple hidden  line eliminator. In  overall
strucuture OCCULT is  a three level hierarcy of methods. At the outer
level there is a [Warnock] like recursive window method,  which calls
an Edge-Edge  compare method  on small enough  windows which  in turn
calls  a Coherent Object method to trace  and mark the portions of an
object that are  hidden. Appended to  the trilevel hierarcy are  four
auxillary techniques: initial elimination by clipping planes, initial
elimination by  face vectors,  initial elimination  by inspection  of
concave corners, and  a final elimination of potential  special cases
(missed by edge-edge  methods) using a pseudo face-vertex method. The
challenging part in building an OCCULT like hidden line eliminator is
getting all  the unruly  beasts in  harness together;  the intriguing
mystery  is that no one  beast is sufficiently  stronger than all the
rest to carry the whole burden expeditiously.{Q}
⊂4.1	Initialization for Hidden Line Elimination.⊃

	A substantial part  of sophisticated hidden  line elimination
lies  in careful attention  to initial preparations.   As  it has now
stood for  the past  two  years, OCCULT  has two  input  restrictions
imposed for  the sake of  execution speed: no conflicting  bodies are
allowed  and no  concave faces are  allowed.   Conflicting bodies are
those that occupy the same space at the same  time; concave faces are
faces with interiors  containing a pair of points  such that the line
segment between  the  points is  not  contained  in the  face.    The
rational for  both these  restrictions is  based on the  optimization
technique  of getting computations  out of inner  loops - conflicting
bodies and  concave  faces can  be  eliminated by  employing  certain
polyhedral construction primitives prior  to hidden line elimination.
The  restrictions   are  not  inherent  limitations  of  any  of  the
techniques  in  OCCULT,  so  that  a  more  unrestricted  but  slower
implementation is feasible.

	OCCULT is essentially a marking algorithm, two of the marking
bits carried in the status word of  every face,  edge and vertex  are
the POTENT bit indicating  that an entity is potentially  visible and
the  VISIBLE bit indicating that  an entity is  actually visible. The
combination (¬POTENT  and ¬VISIBLE) means  that the  entity has  been
found  to be  hidden,   the combination  (POTENT and  VISIBLE) is  an
unused  state  that  happens  to  be  interpreted  as  VISIBLE.   The
initialization can be  regarded as three  marking steps: (1).  vertex
marking  and vertex perspective  projection; (2). face  marking, face
Z-clipping, and  computation of  face coefficients;  and (3).    edge
marking and computation of edge coefficients.

	Vertex initialization includes the  prespective projection of
every vertex in the  model and the marking of every vertex that is in
front of  the  camera as  POTENT  (potentially visible)  with  ZPP(V)
greater than  FOCAL.   Two further  status bits,  named PZZ  and NZZ,
indicating positive Zpp or negative Zpp are IOR'ed into all the faces
and edges of the vertex for the sake of the Z-clipper.

	Face initialization consists  of Z-clipping: if the  face has
only its NZZ bit is on then it is completely behind the camera and is
immediate dropped from  all futher  condsideration; if  the face  has
both its PZZ  and its NZZ turn on  then it is Z-clipped by  using the
camera's  image plane as a  cutting plane. Next for  faces in view of
the camera,   the  3-D perspective  projected  face coefficients  are
computed  and  faces with  their  backsides  towards the  camera  are
dropped,  and faces surviving to this point  are marked as POTENT and
are placed into a list of faces of the first  window of the recursive
window sort.

	Edge initialization consists of computing  the normalized 2-D
edge  coefficients (for  the sake  of  rapid edge-edge  compares) and
marking the edge as FOLDED or ¬FOLDED depending on whether it has one
face POTENT or  two faces POTENT.  FOLDED edges  are then inverted if
necessary  so  that the  POTENT  face is  the PFACE.  Inspite  of the
complexity explained so far, still further measures could be taken to
make the  hidden line elimintator  even faster, For  example more 3-D
clipping or  spatial  recusive cell  sorting  would allow  the  early
elimination of objects that fall outside of purview.

{JC} Normalized 2-D Edge Coefficients:{λ10;JAF3}
		AA(E) ← YPP(PVT(E)) - YPP(NVT(E));
		BB(E) ← XPP(NVT(E)) - XPP(PVT(E));
		CC(E) ← XPP(PVT(E))*YPP(NVT(E)) - XPP(NVT(E))*YPP(PVT(E));
		TMP   ← SQRT(AA(E)↑2 + BB(E)↑2);
		AA(E) ← AA(E)/TMP;
		BB(E) ← BB(E)/TMP;
		CC(E) ← CC(E)/TMP;{λ30;JUFA}

⊂4.2	Hide Marking a Coherent Object.⊃

	OCCULT marks  the faces, edges  and vertices of  a polyhedral
scene as being  either visible or hidden with respect to a simulated
camera.  Edges that  were at first  partially visible are split  into
pieces so that each piece is either fully visible or fully hidden. In
a  modeling environment that provides coherent  polyhedra that can be
easily traveled and  modified, the simple  technique of hide  marking
the neighbors of entities already hidden can be used to do almost all
of the actual hiding, once a starting place has been found.

	In OCCULT,   the two  innermost routines,   EHIDE and  VHIDE,
perform this kind of marking. The routine  VHIDE takes two arguments:
the vertex, V, which  is to be marked as hidden and the face, F, that
is known to  hide V;  the routine  then simply calls  EHIDE for  each
potentially visible edge of V's  perimeter. EHIDE in turn takes three
arguments: an  overface, F,  an edge, E,  and one vertex,  V, of that
edge which is  known to  be hidden by  F.  EHIDE  then checks to  see
whether or not E leaves its overface, F, there are three basic cases:
(i) E does  not leave  F,  so  it is  marked as hidden  and VHIDE  is
applied to  the vertex OTHER(E,V);  (ii) E does  leave overface  F by
crossing under a ¬FOLDED edge which provides a new overface for EHIDE
to check; or (iii) E leaves F by crossing under a <folded> edge,   so
EHIDE splits  the original edge,  E,  and the  folded edge to  form a
T-joint  (defined in next paragraph) marking  the hidden portion of E
as hidden and leaving the remaining portion of E potentially visible.

	A T-joint occurs  in the  image, when a  folded edge hides  a
second  edge  that  is further  away  from  the  camera. When  OCCULT
discovers a T-joint, both edges are  ESPLIT and two new vertices  are
create the further  one is called  the JUT, Joint-Under-T  vertex the
nearer one is called the JOT, Joint-Over-T vertex. Jut and Jots point
at each other using a TJOINT link field.

	There are several techniques for finding starting places, the
major  brute  force  technique  involves  doing  an  edge-edge  or  a
face-vertex compare using all the faces, edges and vertices  that are
potentially visible. One minor technique, involves inspecting concave
corners for hidden edges which can be traced. Another minor technique
is  applicible when  hidden  line  elimination  is being  done  on  a
sequence of image  which are not changing very drasticly from one to
the next;  by saving  a pointer  to the  overface that  covered  each
hidden vertex in  the immediately preceding hidden  line elimination,
the  previous overface  can be  quickly  checked to  see if  it still
covers  the   vertex.  In   one  case,   this   form  of   exploiting
<frame-coherence>   realized  a   twenty-five   percent  savings   in
computation time.

⊂4.3	Edge-Edge and Face-Vertex Comparing.⊃

	Although there are many interesting  ways of comparing faces,
edges and vertices  that are relevant to hidden line elimination; two
particular compares stand  out as most  basic, the edge-edge  compare
and the  face-vertex compare  implemented in procedures  named COMPEE
and COMPFE respectively.

	The edge-edge compare routine, COMPEE,  determines whether or
not  two edges intersect in  the 2-D image coordinates,  XPP and YPP.
The basic edge-edge intersection test requires passing two opposition
conditions: the ends  of one edge must be in  opposite halfplane with
respect  to the line  containing the  other edge and  vice versa. The
halfplane opposition is determined  by two evaluations of  the normal
equation of the  line using the edge coefficients AA,  BB, CC and the
vertex coordinates XPP and YPP. Consquently, it can be assumed that the
two edges cross if the following expression both return negative values:
{λ7;JAF3
}	FLAG1 ←	(AA(E1)*XPP(PVT(E2)) + BB(E1)*YPP(PVT(E2)) + CC(E1))
	    XOR	(AA(E1)*XPP(NVT(E2)) + BB(E1)*YPP(NVT(E2)) + CC(E1));
	FLAG2 ← (AA(E2)*XPP(PVT(E1)) + BB(E2)*YPP(PVT(E1)) + CC(E2))
	    XOR	(AA(E2)*XPP(NVT(E1)) + BB(E2)*YPP(NVT(E1)) + CC(E2));{λ30;JUFA}
\The infix operator XOR is for toggling the sign bits in the same
fashion as a multiplication would in more conventional ALGOL.
When the crossing condition is true, the locus of intersection can be
computed by solving two equations in two unknowns:
{λ7;JAF3
}	TMP	←	(AA(E1)*BB(E2) - AA(E2)*BB(E1));
	XPP(V)	←	(CC(E1)*BB(E2) - CC(E2)*BB(E1))/TMP;
	YPP(V)	←	(AA(E1)*CC(E2) - AA(E2)*CC(E1))/TMP;{λ30;JUFA}
	An alternate edge-edge  compare method would be to  solve the
two  equations in  two unknowns  first  and then  to see  whether the
intersection locus is  interior to the line  segments of both  edges.
Since,  disjoint  pairs of  edges  occur  much more  frequently  than
intersecting  edge,  the  alternate  method  requires  more  floating
arithmetic operations on the average than the first  method which can
discover  about  half of  the  disjoint  cases  in computing,  FLAG1.
Furthermore  the   alternate  method   does   not  lend   itself   to
distinguihing the almost touching cases.

{|;λ10;JAFA}
BOX 4.X {JC} Edge-Edge Compare Steps.

	i.	Test for Identity.
	ii.	Test for Topological connection.
		(Edges already having a vertex of T-joint in common).
	iii.	Test for span Overlap in XPP and YPP.
		To prevent nasty colinear cases.
	iv.	Compare for crossing ?	Ends/Lines Opposition Tests.
	v.	Fudge (Move towards right and down).
{|;λ30;JUFA}

	The face-vertex compare routine, COMPFE has two parts Z-depth
compare for vertex under the plane of the face and 2-D within compare
for vertex enclosure by the face perimeter. The first compare is done
by evaluating the Z-depth of the  vertex with respect to the plane of
the face. Since faces are convex and since polyhedra are oriented the
properly directed edges coefficient  can be used to test  whether the
vertex falls outside  of the face for any of  the edges of the face's
perimeter. The Z-depth test is performed first because it is quicker.

	Two very simple  important kinds of  hidden line  eliminators
that  almost work  are  based  on  combining edge-edge  comparing  or
face-vertex comparing with coherent object hidding.

⊂4.4	Recursive Windowing.⊃

	Recursive  Windowing is  a  two dimensional  spatial  sorting
technique for partitioning  the faces,  edges and vertices associated
with a  rectangular  region  called  a window  into  two  subwindows.
recursively  until  a  desired   condition  is  achieved.  The  usual
termination condition is that the population of entites in the window
becomes sufficiently low or  that the window becomes small.  The idea
is  implement in a  routine called  ESORT which resembles  the hidden
line eliminators of [Warnock] and [Sutherland  68],
however ESORT is unique  in that it maintains a  data structure which
allows  edges to  be  split during  the sort.  The  potentially nasty
fixups are  accomplished  using a  data  structure that  maintains  a
coherent image  of both windows  and edges. Metaphorically,  the data
structure is a cloth with a warp of windows and a woof of edges, each
thread bound to a fiber by a bead.

	<Window Structure>. The  sort window itself is a  twelve word
node  which contains data  fields named XLO,  XHI, YLO  and YHI which
specify the  boundary of  the window  and data  fields named  PENCNT,
SURCNT,   EDGCNT  and VCNT  which specify  the number  of faces  that
penetrate  or surround  the window,   the  number of edges  that pass
through the window  and the number of  vertices that fall within  the
window. The  window contains sufficient link fields  to hold pointers
to the head of  the pen-face list,   the sur-face  list,  the  vertex
list,   the head  and tail  of its  edge list  and a  pointer to  its
antecedent window.

	<Bead Structure>.  A bead is  a two  word node that  contains
four  pointers and which represents  one instance of  an edge passing
through a  window. Each  edge has  a list  of  beads representing  an
ordered list  of the window through  which it (the edge)  passes; and
each  window has a list of beads representing  a list of the edges it
contains.  The link fields named WND and EDG of a bead,  point to the
particular window and the  particular edge to which the bead belongs.
The link fields named WNBL and  EDBL of a bead contain the  necessary
links for the window's bead list and for the edge's bead list.

{|;λ10;JAFA}
BOX 4.X {JC} RECURSIVE WINDOWING ROUTINES.
	1.	MKSWN	Make Sort Window.
	2.	PSHSWN	Push Sort Window.
	3.	PENSUR	Update penetrator and surrounder lists.
	4.	POPSWN	Pop Sort Window.
	5.	BLED	Bead List Edit.
{|;λ30;JUFA}
⊂4.5	Photometric Modeling and Video Generation.⊃

	The light scattering  properties of ordinary surfaces  can be
modeled  by  thinking  of the  surface  as  composed  of many  little
mirrors. The orientation of each  mirror is described by two  angles,
its tilt from the normal vector of  the surface and its pan about the
normal  vector with  respect to a  specified reference  vector in the
tangent plane of  the surface. For  a perfect reflecting surface  all
the  differential mirrors  have a  zero pan  and tilt;  for isotropic
conventional   surfaces   the   statistical   distribution   of   pan
orientations is flat and  the distribution of tilt orientations  is a
blip function; and  for a perfect isotropic Lambert surfaces both the
pan and tilt distributions are flat.

(Propagating Underfaces and Shadows.)

⊂4.6	Performance of OCCULT and Related Work.⊃